#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    int ans1(vector<vector<int>>& grid){
        int m = grid.size();
        vector<vector<int>> dp(m);
        int MIN = INT32_MAX;
        if(m == 1){
            return grid[0][0];
        }
        for(int i = 0; i != m; i++){
            int n = grid[i].size();
            if(n == 1){
                dp[i].push_back(grid[i][0]);
            }
            else{
                for(int j = 0; j != n; j++){
                    int min_val;
                    if(j == 0){
                        dp[i].push_back(dp[i-1][0] + grid[i][0]);
                        min_val = dp[i-1][0] + grid[i][0];
                    }else if(j == n-1){
                        dp[i].push_back(dp[i-1][j-1] + grid[i][j]);
                        min_val = dp[i-1][j-1] + grid[i][j];
                    }else{
                        min_val = min(dp[i-1][j-1]+grid[i][j], dp[i-1][j]+grid[i][j]);
                        dp[i].push_back(min_val);
                    }
                    if(i == m-1){
                        MIN = min(MIN, min_val);
                    }
                }
            }
        }

        return MIN;
    }
};

void test(){
    Solution s;
    vector<vector<int>> grid = {
        {2},
        {3,4},
        {6,5,7},
        {4,1,8,3}
    };

    int ret = s.ans1(grid);
    cout << ret << endl;
}

int main(void){
    test();

    return 0;
}